#include "DynamicArray.h"


struct DynamicArray
{
    ElementType *array;//数组指针
    int capacity;//数组容量
    int size;//元素个数 
};

DArray *InitDArray()
{
    DArray *a=(DArray*)malloc(sizeof(DArray));
    if(a==NULL)
    {
        printf("InitDarray malloc error!");
        exit(-1);//退出程序
    }
    a->size = 0;
    a->capacity=10;
    a->array=(ElementType*)malloc(sizeof(ElementType)*a->capacity);
    if(a->array==NULL)
    {
        printf("InitDarray malloc error!");
        exit(-1);
    }
    printf("\n");
    return a;
}

void InsertDArray(DArray * a, ElementType element)
{
    if(a->size == a->capacity)
    {
        a->capacity *= 2;
        a->array=(ElementType*)realloc(a->array, a->capacity*sizeof(ElementType));
        if(a->array == NULL)
        {
            printf("InsertDArray realloc error!\n");
            exit(-1);
        }
       
    }
     a->array[a->size++]= element;
}

void PrintDArray(DArray *a, void (*print)(ElementType))
{
    printf("capacity:%d size: %d\n",a->capacity,a->size);
    for(int i=0;i< a->size; i++)
    {
        print(a->array[i]);       
    }
    printf("\n");
}


ElementType FindByElement(DArray *a,ElementType value,bool(*compaer)(ElementType,ElementType))
{
    for(int i=0;i<a->size;i++)
    {
        if(compaer(a->array[i],value))
        return a->array[i];
    }
    return NULL;
}

ElementType RemoveByIndex(DArray *a,int index)
{
    ElementType result=a->array[index];
    for(int i = index; i<a->size - i; i++)
    {
        a->array[i]=a->array[i=1];
    }
    a->size--;
    return result;
}


ElementType RemoveDArray(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for(int i=0;i<a->size;i++)
    {
        if(compare(a->array[i],value))
        {
            return RemoveByIndex(a,i);
        }
    }
    return NULL;
}





void MyFastSort(ElementType *a, int start, int end, bool(*compare)(ElementType,ElementType))
{
    if(start >= end);    //终止条件
    return;
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        //从右往左找比基准值小的
        while(compare(a[right]>temp) && left < right)
            right--;
        if(left <right)
            a[left++]=a[right]; //把比基准值小的数放到左边
        //从左往右找比基准值大的
        while(compare(temp,a[left]) < temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];//把比基准值大的数放右边
    }
    a[left] = temp;

    MyFastSort(a,start,left - 1,compare);
    MyFastSort(a,right+1,end,compare);
}

void FastSort(DArray *a, bool(*compare)(ElementType, ElementType))
{
    MyFastSort(a->array,0,a->size-1,compare);
}

void ClearDArray(DArray *a, void(*clear)(ElementType))
{
    if(a != NULL)
    { 
        for(int i=
        0;i<a->size;i++)
        {
            clear(a->array[i]);
        }
        free(a->array);
        free(a);
    }
   
}

ElementType BinarySearch(DArray *a, ElementType value, int(*compare)(ElementType, ElementType)) //二分排序
{
    int left =0;
    int right = size-1;
    while(left<=right)
    {
        int mid = left +(right-left)/2;
        //(left & right)+((left ^ right)>>1);
        if(compare(a->array[mid],value)==0)
        {
            return mid;
        }
        else if(compare(a->array[mid],value)>0)
        {
            right=mid-1;
        }
        else if(compare(a->array[mid],value)<0)
        {
            left=mid + 1;
        }
    }
    return NULL;
}

